package com.wzh.test.dynamicprograming;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * 现在有一个4公斤的背包
 * 有一个电子琴 重 1公斤 价值1000元
 * 有一个钢琴  重2公斤  价值1500元
 * 有一个电脑   重三公斤  价值 3000元
 *
 * 问：在背包承受范围之内，要求装入的价值最多，请问应该如何放入
 */
public class Demo3 {
    public static void main(String[] args) {
        int bgWeight = 4;
        ArrayList<Goods> arrayListGoods = new ArrayList<>(3);
        arrayListGoods.add(new Goods(1,1000));
        arrayListGoods.add(new Goods(2,1500));
        arrayListGoods.add(new Goods(3,3000));

        int result = maxValue(arrayListGoods,bgWeight);
        System.out.println(result);


    }

    public static int maxValue(ArrayList<Goods> arrayListGoods,int bgWeight){
        //定义一个二维数组，存放每一种情况的数据
         int[][] subSet = new int[arrayListGoods.size()][bgWeight+1];
         //第0列都是0，默认
        //第0行都是第0个物品的价值
        for(int j = 1; j < bgWeight + 1;j++){
            subSet[0][j] = arrayListGoods.get(0).value;
        }

        for(int i = 1;i < arrayListGoods.size();i++){
            for(int j = 1; j < bgWeight + 1;j++){

                Goods nowGoods = arrayListGoods.get(i);
                if(nowGoods.weight > j){
                    //如果当前货物的重量小于背包的重量，则这个背包里能放的是上一个物品+剩余空间能放的物品
                    //上一个物品
                    subSet[i][j] = subSet[i-1][j];
                }else{
                    //如果当前货物的重量大于背包的重量，则这个背包里能放的是上一个物品+剩余空间能放的物品  || 当前物品 + 剩余空间能放物品的最大值
                    //上一个物品
                    int prevValue = subSet[i-1][j];
                    //剩余空间放的物品
                    //当前物品
                    int nowValue = nowGoods.value;
                    //放入当前物品后，剩余空间能放的物品
                    int nowLeaveValue = 0;
                    if(j > nowGoods.weight){
                        nowLeaveValue = subSet[i - 1][j - nowGoods.weight];
                    }

                    subSet[i][j] = Math.max(nowValue + nowLeaveValue,prevValue);
                }
            }
        }

        for(int i = 0; i < subSet.length;i++){
            System.out.println(Arrays.toString(subSet[i]));
        }

        return subSet[arrayListGoods.size() - 1][bgWeight];
    }
}

class Goods{
    public int weight;
    public int value;

    public Goods(int weight, int value) {
        this.weight = weight;
        this.value = value;
    }
}
